/**
 * 剑指 Offer 30. 包含min函数的栈
 * https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/
 */

/**
 * @param {number} target
 * @param {number[]} sortedIndexes
 * @param {number[]} nums
 */
function findIndex(target, sortedIndexes, nums) {
  let left = 0;
  let right = sortedIndexes.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const midVal = nums[sortedIndexes[mid]];
    if (target === midVal) {
      return mid;
    }
    if (target > midVal) {
      left = mid + 1;
    } else {
      if (!mid || nums[sortedIndexes[mid - 1]] < target) {
        return mid;
      }
      right = mid - 1;
    }
  }
  return left;
}

/**
 * initialize your data structure here.
 */
const MinStack = function () {
  this.stack = [];
  this.sortedIndexes = [];
};

/**
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function (x) {
  const insertIndex = findIndex(x, this.sortedIndexes, this.stack);
  this.sortedIndexes.splice(insertIndex, 0, this.stack.length);
  this.stack.push(x);
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function () {
  const removedIndex = this.sortedIndexes.indexOf(this.stack.length - 1);
  this.sortedIndexes.splice(removedIndex, 1);
  this.stack.pop();
};

/**
 * @return {number}
 */
MinStack.prototype.top = function () {
  return this.stack[this.stack.length - 1];
};

/**
 * @return {number}
 */
MinStack.prototype.min = function () {
  return this.stack[this.sortedIndexes[0]];
};

const minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
console.log(minStack.min() === -3);
minStack.pop();
console.log(minStack.top() === 0);
console.log(minStack.min() === -2);
